package main

func main() {

	//打印测试用例返回结果
	resp := climbStairs2(44)
	println(resp)

}

func climbStairs(n int) int {
	if n == 1 || n == 2 {
		return n
	}
	//滑动数组方法，将本来的“备忘录”O(n)的空间复杂度降为O(1)
	first, second, ans := 1, 2, 0
	for i := 3; i <= n; i++ {
		ans = first + second
		first = second
		second = ans
	}
	return ans
}

func climbStairs2(n int) int {
	//建立一个map数据结构，其他语言同理
	rememberMap := make(map[int]int)
	return climbStairs_Remember(n, rememberMap)

}

func climbStairs_Remember(n int, rememberMap map[int]int) int {
	if n == 1 || n == 2 {
		return n
	}
	//exist是布尔类型，如果是true代表map里存在该键；value代表键对应的值.
	value, exist := rememberMap[n]
	if exist {
		return value
	} else {
		result1 := climbStairs_Remember(n-1, rememberMap)
		result2 := climbStairs_Remember(n-2, rememberMap)
		//将result1和result2添加进map的键值对中：
		rememberMap[n] = result1 + result2
		return rememberMap[n]
	}

}
